UVa/11665 - Chinese Ink/11665.3.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 #define EPS 1e-9
  29
  30 typedef pair<int, int> point;
  31 typedef vector< point > polygon;
  32
  33 vector< polygon > polygons;
  34
  35 const int MAXN = 50;
  36 int p[MAXN];
  37
  38 int find(int u) {
  39     return p[u] == u ? u : p[u] = find(p[u]);
  40 }
  41
  42 void link(int u, int v) {
  43     if (find(u) != find(v)) {
  44         p[find(u)] = find(v);
  45     }
  46 }
  47
  48 // Polar angle
  49 // Returns an angle in the range [0, 2*Pi) of a given Cartesian point.
  50 // If the point is (0,0), -1.0 is returned.
  51 // REQUIRES:
  52 // include math.h
  53 // define EPS 0.000000001, or your choice
  54 // P has members x and y.
  55 double polarAngle( point p ) {
  56     double x = p.first, y = p.second;
  57     if(fabs(x) <= EPS && fabs(y) <= EPS) return -1.0;
  58     if(fabs(x) <= EPS) return (y > EPS ? 1.0 : 3.0) * acos(0);
  59     double theta = atan(1.0 * y / x);
  60     if(x > EPS) return(y >= -EPS ? theta : (4*acos(0) + theta));
  61     return(2 * acos( 0 ) + theta);
  62 }
  63
  64 //Point inside polygon
  65 // Returns true iff p is inside poly.
  66 // PRE: The vertices of poly are ordered (either clockwise or
  67 //      counter-clockwise.
  68 // POST: Modify code inside to handle the special case of "on
  69 // an edge".
  70 // REQUIRES:
  71 // polarAngle()
  72 // include math.h
  73 // include vector
  74 // define EPS 0.000000001, or your choice
  75 bool pointInPoly( point p, const polygon &poly ) {
  76   int n = poly.size();
  77   double ang = 0.0;
  78   for(int i = n - 1, j = 0; j < n; i = j++){
  79     point v( poly[i].first - p.first, poly[i].second - p.second );
  80     point w( poly[j].first - p.first, poly[j].second - p.second );
  81     double va = polarAngle(v);
  82     double wa = polarAngle(w);
  83     double xx = wa - va;
  84     if(va < -0.5 || wa < -0.5 || fabs(fabs(xx)-2*acos(0)) < EPS){
  85         // POINT IS ON THE EDGE
  86         return true;
  87         assert( false );
  88         ang += 2 * acos( 0 );
  89         continue;
  90       }
  91     if( xx < -2 * acos( 0 ) ) ang += xx + 4 * acos( 0 );
  92     else if( xx > 2 * acos( 0 ) ) ang += xx - 4 * acos( 0 );
  93     else ang += xx;
  94   }
  95   return( ang * ang > 1.0 );
  96 }
  97
  98
  99 /*
 100   Returns true if point (x, y) lies inside (or in the border)
 101   of box defined by points (x0, y0) and (x1, y1).
 102 */
 103 bool point_in_box(double x, double y,
 104                   double x0, double y0,
 105                   double x1, double y1){
 106   return
 107     min(x0, x1) <= x && x <= max(x0, x1) &&
 108     min(y0, y1) <= y && y <= max(y0, y1);
 109 }
 110
 111
 112 /*
 113   Finds the intersection between two segments (Not infinite
 114   lines!)
 115   Segment 1 goes from point (x0, y0) to (x1, y1).
 116   Segment 2 goes from point (x2, y2) to (x3, y3).
 117
 118   (Can be modified to find the intersection between a segment
 119   and a line)
 120
 121   Handles the case when the 2 segments are:
 122   *Parallel but don't lie on the same line (No intersection)
 123   *Parallel and both lie on the same line (Infinite
 124   *intersections or no intersections)
 125   *Not parallel (One intersection or no intersections)
 126
 127   Returns true if the segments do intersect in any case.
 128 */
 129 bool segment_segment_intersection(int x1, int y1,
 130                                   int x2, int y2,
 131
 132                                   int x3, int y3,
 133                                   int x4, int y4){
 134
 135     int d1 = (x1 - x3) * (y4 - y3) - (y1 - y3) * (x4 - x3);
 136     int d2 = (x2 - x3) * (y4 - y3) - (y2 - y3) * (x4 - x3);
 137     int d3 = (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1);
 138     int d4 = (x4 - x1) * (y2 - y1) - (y4 - y1) * (x2 - x1);
 139
 140     bool b1 = d1 > 0 and d2 < 0 or d1 < 0 and d2 > 0;
 141     bool b2 = d3 > 0 and d4 < 0 or d3 < 0 and d4 > 0;
 142     if (b1 and b2) return true;
 143     if (d1 == 0 and point_in_box(x1, y1,   x3, y3, x4, y4)) return true;
 144     if (d2 == 0 and point_in_box(x2, y2,   x3, y3, x4, y4)) return true;
 145     if (d3 == 0 and point_in_box(x3, y3,   x1, y1, x2, y2)) return true;
 146     if (d4 == 0 and point_in_box(x4, y4,   x1, y1, x2, y2)) return true;
 147     return false;
 148 }
 149
 150 bool polygonsIntersect(const polygon &a, const polygon &b) {
 151     int na = a.size(), nb = b.size();
 152     for (int i = 0; i < na; ++i) {
 153         if (pointInPoly(a[i], b)) return true;
 154     }
 155     for (int i = 0; i < nb; ++i) {
 156         if (pointInPoly(b[i], a)) return true;
 157     }
 158
 159     for (int i = 0; i < na; ++i) {
 160         for (int j = 0; j < nb; ++j) {
 161             int xa1 = a[i].first, ya1 = a[i].second;
 162             int xa2 = a[(i + 1) % na].first, ya2 = a[(i + 1) % na].second;
 163             int xb1 = b[j].first, yb1 = b[j].second;
 164             int xb2 = b[(j + 1) % nb].first, yb2 = b[(j + 1) % nb].second;
 165             if (segment_segment_intersection(xa1, ya1,    xa2, ya2,               xb1, yb1, xb2, yb2)) {
 166                 return true;
 167             }
 168         }
 169     }
 170
 171
 172     return false;
 173 }
 174
 175
 176 void solve() {
 177     int n = polygons.size();
 178     for (int i = 0; i < n; ++i) {
 179         p[i] = i;
 180     }
 181
 182     for (int i = 0; i < n; ++i) {
 183         for (int j = i + 1; j < n; ++j) {
 184             if (polygonsIntersect(polygons[i], polygons[j])) {
 185                 link(i, j);
 186             }
 187         }
 188     }
 189     set<int> ans;
 190     for (int i = 0; i < n; ++i) {
 191         ans.insert(find(i));
 192     }
 193     cout << ans.size() << endl;
 194 }
 195
 196
 197 int main(){
 198     int n;
 199     while (cin >> n) {
 200         if (n == 0) break;
 201         string s; getline(cin, s);
 202         polygons.clear();
 203         for (int i = 0; i < n; ++i){
 204             polygons.push_back(polygon());
 205             getline(cin, s);
 206             stringstream sin(s);
 207             int x, y;
 208             while (sin >> x >> y) {
 209                 polygons.back().push_back(point(x, y));
 210             }
 211             assert(polygons.back().size() >= 3);
 212         }
 213         assert(polygons.size() == n);
 214
 215         solve();
 216     }
 217     return 0;
 218 }